package main

func trap(height []int) int {
	n := len(height)
	if n == 0 {
		return 0
	}
	left := make([]int, n)
	right := make([]int, n)
	solid, water := 0, 0

	currHeight := -1
	for i := 0; i < n; i++ {
		solid += height[i]
		if height[i] > currHeight {
			currHeight = height[i]
		}
		left[i] = currHeight
	}

	currHeight = -1
	for i := n - 1; i >= 0; i-- {
		if height[i] > currHeight {
			currHeight = height[i]
		}
		right[i] = currHeight
	}

	for i := 0; i < n; i++ {
		if left[i] < right[i] {
			water += left[i]
		} else {
			water += right[i]
		}
	}
	return water - solid
}
